//给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符
//合要求的单词则返回空字符串。 
//
// 示例： 
//
// 输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
//输出： "dogwalker"
//解释： "dogwalker"可由"dog"和"walker"组成。
// 
//
// 提示： 
//
// 
// 0 <= len(words) <= 200 
// 1 <= len(words[i]) <= 100 
// 
//
// Related Topics 字典树 数组 哈希表 字符串 👍 63 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-09-16 23:16:08
 * @description 面试题 17.15.最长单词
 */
public class LongestWordLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LongestWordLcci fun=new LongestWordLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
排序：单词按长度升序和字典序降序排序，确保先处理短单词，且相同长度时字典序大的先处理（便于后续替换为字典序小的结果）。
哈希集合：使用集合存储所有单词，便于快速查找子串是否存在。
动态规划检查：canForm方法使用动态规划数组dp，其中dp[i]表示前i个字符能否被组合。
遍历所有可能的分割点j，如果前j个字符可组合且子串words[j:i]在集合中，则标记dp[i]为true。
更新结果：对于每个单词，暂时从集合中移除，检查是否能由其他单词组合。
如果能，且长度更长或字典序更小，则更新结果。最后将单词重新加入集合。
		 * */
	public String longestWord(String[] words) {
		Arrays.sort(words, (a, b) -> {
			if (a.length() != b.length()) {
				return b.length() - a.length(); // 长的在前面
			} else {
				return a.compareTo(b); // 相同长度，字典序小的在前面
			}
		});

		Set<String> set = new HashSet<>(Arrays.asList(words));
		String res = "";
		for (String word : words) {
			set.remove(word);
			if (canForm(word, set)) {
				return word;
//				if (word.length() > res.length() || (word.length() == res.length() && word.compareTo(res) < 0)) {
//					res = word;
//				}
			}
			set.add(word);
		}
		return res;
	}

	private boolean canForm(String word, Set<String> set) {
		if (set.isEmpty()) return false;
		int n = word.length();
		boolean[] dp = new boolean[n + 1];
		dp[0] = true;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				if (dp[j] && set.contains(word.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[n];
	}
	/*
Trie结构：
	TrieNode 类表示字典树的节点，包含26个子节点数组和一个标记是否单词结束的布尔值。
	Trie 类包含根节点和插入方法，用于构建字典树。
排序策略：
	单词按长度降序排序，这样优先检查最长的单词。
	长度相同时按字典序升序排序，这样优先返回字典序较小的单词。
DFS检查：
	canForm 方法使用DFS来检查单词是否可由其他单词组成。
	start 参数表示当前检查的起始位置。
	count 参数表示已经使用的单词数量。
	当遇到一个单词结尾时，可以选择分割（递归调用）或继续当前单词。
	到达字符串末尾时，需要确保至少使用了2个单词（count >= 1）。
提前返回：
	由于排序策略，一旦找到符合条件的单词就直接返回，确保得到最长的且字典序最小的结果。
	* */

	public String longestWord2(String[] words) {
		// 构建字典树
		Trie trie = new Trie();
		for (String word : words) {
			trie.insert(word);
		}

		// 按长度降序，长度相同按字典序升序排序
		Arrays.sort(words, (a, b) -> {
			if (a.length() != b.length()) {
				return b.length() - a.length();
			} else {
				return a.compareTo(b);
			}
		});

		// 检查每个单词是否可以由其他单词组成
		for (String word : words) {
			if (trie.canForm(word, 0, 0)) {
				return word;
			}
		}

		return "";
	}


	class Trie {
		Trie[] children;
		boolean isEnd;

		Trie() {
			children = new Trie[26];
			isEnd = false;
		}

		void insert(String word) {
			Trie node = this;
			for (char c : word.toCharArray()) {
				int idx = c - 'a';
				if (node.children[idx] == null) {
					node.children[idx] = new Trie();
				}
				node = node.children[idx];
			}
			node.isEnd = true;
		}

		boolean canForm(String word, int start, int count) {
			Trie node = this;
			for (int i = start; i < word.length(); i++) {
				int idx = word.charAt(i) - 'a';
				if (node.children[idx] == null) {
					return false;
				}
				node = node.children[idx];

				// 如果当前是一个单词的结尾
				if (node.isEnd) {
					// 如果已经到达字符串末尾
					if (i == word.length() - 1) {
						// 必须由至少2个单词组成（count >= 1）
						return count >= 1;
					}
					// 尝试从下一个位置开始新的单词
					if (canForm(word, i + 1, count + 1)) {
						return true;
					}
				}
			}
			return false;
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
